/*
leetcode 1：两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

 

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
 

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
 

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
*/
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {

    unordered_map<int, int> numMap; // 用于存储数字和它的索引

   //遍历数组 nums，从索引 i = 0 开始，直到数组的最后一个元素
    for (int i = 0; i < nums.size(); ++i) {

        int complement = target - nums[i]; // 计算当前数字需要的补数
        
        //检查哈希表中是否存在补数 complement。如果找到了，表示我们已经找到了一对数字，
        //它们的和为 target。find 函数用于查找哈希表中是否存在给定的键（complement）。
        //如果存在，find 会返回一个指向该元素的迭代器，否则返回 end()。
        if (numMap.find(complement) != numMap.end()) {

            return {numMap[complement], i}; // 返回补数的索引和当前数字的索引，找到了就直接返回不需要继续找了
        }
        //它的键是数组中的元素，值是该元素的索引。
        //通过 numMap[nums[i]] = i，我们将当前元素 nums[i] 的值作为键，将其索引 i 作为值存储在哈希表中。
        numMap[nums[i]] = i; 
    }
    return {}; // 如果没有找到符合条件的结果，返回空数组
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(nums, target);
    
    if (!result.empty()) {
        cout << "Indices: " << result[0] << ", " << result[1] << endl;
    } else {
        cout << "No solution found!" << endl;
    }

    return 0;
}

/*
假设输入数组 nums = [2, 7, 11, 15] 和目标值 target = 9。

步骤 1：初始化哈希表
unordered_map<int, int> numMap; 这里创建了一个哈希表 numMap，它的键（key）是数组中的元素，值（value）是该元素的索引。哈希表的作用是快速查找数组中是否已经存在与当前数字相加等于目标值的数字。

步骤 2：遍历数组
我们开始遍历数组 nums。

第一次迭代（i = 0，nums[i] = 2）：
计算补数：complement = target - nums[0] = 9 - 2 = 7。
检查哈希表中是否有 complement = 7：
numMap.find(7) 返回 numMap.end()，表示没有找到补数。
将 nums[0] = 2 和它的索引 0 存入哈希表：numMap[2] = 0。
当前哈希表状态：numMap = {2: 0}。

第二次迭代（i = 1，nums[i] = 7）：
计算补数：complement = target - nums[1] = 9 - 7 = 2。
检查哈希表中是否有 complement = 2：
numMap.find(2) 返回 numMap[2] = 0，表示找到了补数 2，它的索引是 0。
找到符合条件的两个数字：nums[0] = 2 和 nums[1] = 7，它们的和是 9。
返回这两个索引：return {numMap[2], 1}，即返回 [0, 1]。
*/